package 力扣._3243_新增道路查询后的最短距离1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {

    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        // bfs
        int[] result = new int[queries.length];
        List<List<Integer>> m = new ArrayList<>();
        for(int i=0;i<n-1;i++){
            List<Integer> row = new ArrayList<>();
            row.add(i+1);
            m.add(row);
        }
        m.add(new ArrayList<>());

        for(int k = 0;k<queries.length;k++){
            int[] query = queries[k];
            m.get(query[0]).add(query[1]);
            Deque<Integer> queue = new ArrayDeque<>();
            queue.add(0);
            int[] visited = new int[n];
            int step = 0;
            int dis_n = 0;



            while(!queue.isEmpty()){
                int step_size = queue.size();
                for(int i=0;i<step_size;i++){
                    int cur = queue.poll();
                    visited[cur] = 1;
                    if(cur==n-1){
                        dis_n = step;
                        break;
                    }
                    for(int j: m.get(cur)){
                        if(visited[j]==0){
                            queue.add(j);
                            visited[j] = 1;
                        }
                    }
                }
                step++;
                if(dis_n!=0)
                    break;
            }
            result[k] = dis_n;
        }
        return result;

        
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int n = 5;
        int[][] queries = {{2,4},{0,2},{0,4}};
        int[] result = s.shortestDistanceAfterQueries(n, queries);
        for(int i=0;i<result.length;i++){
            System.out.println(result[i]);
        }
    }
}